perm filename K.TEX[TEX,DEK] blob
sn#415919 filedate 1979-02-05 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00012 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 \chcode'45 ← 5 % Now `%' works for comments
C00006 00003 % Define the fonts and output routine
C00009 00004 % introduction
C00016 00005 % movement and notation
C00025 00006 % analysis - beginning kings together
C00033 00007 % king in one or two quadrants
C00038 00008 % the rook is or can be safe one rank, two rank
C00044 00009 % three rank,four rank
C00051 00010 % Big regions
C00053 00011 % conclusion
C00057 00012 \vskip 10pt
C00060 ENDMK
C⊗;
\chcode'45 ← 5 % Now `%' works for comments
\chcode'173←1 \chcode'176←2 % `{' and `}' are the grouping characters
\chcode'44←3 % `$' is the math mode symbol
\chcode'26←4 % `⊗' for alignments
\chcode'43←6 % `#' for macro definitions
\chcode'136←7 \chcode 1←8 % `↑' and `↓' for super- and subscripting
\def\null{\hjust{}} % empty box
% ctrline centers the line it is given
\def\ctrline#1{\hjust to size{\hskip0pt plus1000cm minus1000cm
#1\hskip0pt plus1000cm minus1000cm}}
\def\lft#1{#1\hfill} % left justifies whatever #1 is
\def\rgt#1{\hfill#1} % right justifies whatever #1 is
\def\ctr#1{\hfill#1\hfill} % centers whatever #1 is (horizontally)
\def\vctr#1{\vfill#1\vfill} % centers whatever #1 is (vertically)
% For superposition of characters.
\def\spose#1{\hjust to 0pt
{\hskip 0pt minus 100pt #1\hskip 0pt minus 10000000pt}}
% This macro is used to form the chess board with algebraic notation
\def\square#1#2#3{\spose{\ctr{\hskip 3pt\eightpt\bd #1#2}}{\chess #3}}
% These macros are used to refer to figures
\def\fig#1{Figure\penalty 1000\ \penalty 1000 #1}
\def\figs#1{Figures\penalty 1000\ \penalty 1000 #1}
% This macro is used for moves in the text
\def\move#1#2#3#4{\hjust{#1--#2#3#4}}
\def\_{\penalty1000\ \penalty1000 }
% This macro forms the title line of a figure.
\def\figtitle#1{\vjust{\baselineskip 9pt
\hjust to 115pt{\ctr{\eightpt\bd Fig. \count1}}
\advcount1
\hjust to 115pt {\eightpt\rm \ctr{#1}}}}
\setcount1 1
% This macro forms the caption of figure
\def\caption#1{\baselineskip 8pt
\eightpt\rm \hjust to 115pt{\lft{#1}}}
% This macro does underlining
\def\understep#1{$\underline{\hjust{#1}}$}
% This macro is the symbol for a checkmate
\def\cm{\hjust to 10pt{\ctr{\spose
{\vjust to 7pt{\vfill\hrule width7pt\vfill\hrule width7pt\vfill
}}\hjust to 7pt{\hfill\vrule height7pt\hfill\vrule height7pt\hfill}}}}
% This is the symbol for a check
\def\ch{\hjust to 10pt{\ctr{\spose
{\vjust to 7pt{\vfill\hrule width7pt\vfill
}}\hjust to 7pt{\hfill\vrule height7pt\hfill}}}}
% This is the symbol for a draw
\def\dr{\hjust to 10pt{\ctr{\vjust to 7pt{\vfill\hrule width7pt\vfill\hrule
width7pt\vfill}}}}
\def\ldots{{.\≥.\≥.}}
\def\xskip{\hskip 7pt plus3pt minus 4pt} % extra space in text
% Define the fonts and output routine
% These 13 fonts are pre-loaded in the system
\:@←cmathx
\:a←cmr10 \:d←cmr7 \:f←cmr5
\:g←cmi10 \:j←cmi7 \:l←cmi5
\:n←cms10
\:q←cmb10
\:u←cmsy10 \:x←cmsy7 \:z←cmsy5
\:?←cmti10
% Define the fonts used in math mode;
\mathrm adf
\mathit gjl
\mathsy uxz
\mathex @
% The following fonts are used here but not pre-loaded
\:b←cmr8 % 8pt roman
\:r←cmb8 % 8pt bold
\:o←cms8 % 8pt text italic
\:=←fchs50[tex,jeb] % chess font
% These are the macros that will be used for changing fonts
\def\tenpt{ \def\rm{\:a} \def\bd{\:q} \def\it{\:?}}
\def\eightpt{\def\rm{\:d} \def\bd{\:r} \def\it{\:↑}}
\def\chess{\:=}
\parindent 20pt % indent paragraphs 20pt
\maxdepth 2pt % maximum depth of a page
\topbaseline 10pt % distance from top of page
\parskip 0pt plus 1 pt % glue between paragraphs
\baselineskip 12pt % space baselines 12pt apart
\lineskip 1pt % or 1pt down if that won't work
\dispskip 3pt plus 1pt minus 1pt % glues for around displays
\dispaskip 3pt plus 1pt minus 1pt % glues for around displays
\dispbskip 3pt plus 1pt minus 1pt % glues for around displays
\topskip 6pt plus 2pt minus 1pt % glues for under figures at top
\botskip 6pt plus 2pt minus 1pt % glues for above figures at bottom
\output{\baselineskip 20pt\page\ctrline{\:a\count0}\advcount0}
\setcount0 1
\hsize 353pt % Undocumented sizes, but they seem right on the XGP
\vsize 478pt
\null\vskip-12pt % allows glue at top of first page
\tenpt\rm % set font to roman 10pt
% introduction
\ctrline{\understep{A} \understep{KRIEGSPIEL} \understep{ENDGAME}}
\vskip 6pt plus 6pt
\ctrline{by Jim Boyce}
\ctrline{Computer Science Department}
\ctrline{Stanford University}
\vskip 12pt plus 12pt
\noindent Kriegspiel is one of the most interesting variants of chess:
Each player tries to mate his opponent, using ordinary chessmen and following
the ordinary rules, but neither player knows where the other player's pieces
are. Instead, both players have a concealed board on which they can keep track
of their own position and guess at the locations of the opponent's pieces.
There is also a third participant in the game, namely the kriegspiel referee;
he has a third set of chessmen, on which he keeps the actual position. When
it is White's move, White suggests a possible move to the referee. If it is
legal in the actual game position, it becomes White's official move; otherwise
White must try additional moves until one is legal. Then it is Black's turn,
and the game continues in the same way. Any legal move that places the opposing
king in check is announced to both players.
There are other rules (which do not concern us) that involve captures and pawn
moves; further details can be found in [reference].
This article analyzes the ending king and rook vs. king in kriegspiel. In
normal chess, this is well known to be an elementary mate [reference BCE],
but the problem is by no means simple under the kriegspiel ground rules.
In fact, experienced chess players have been known to spend hours on this
problem without resolving it. Therefore the reader is encouraged to try his
own hand at the task before looking at the solution below.
\vskip 3.5pt
\penalty 0
% movement and notation
{\bd Movement and Notation.}\xskip In this article, White has a king and a rook;
Black has only his king. Moves are written in a version of algebraic
notation, in which the files are lettered a--h starting at White's
left and the ranks are
numbered 1--8 starting at White's end of the board.\xskip(See \fig 1.)\xskip
All figures show the board as White sees it: the known locations of his
pieces are marked, and each possible location for the Black king is marked.
\vskip 3pt
\hjust to size{\hfill
\lower 7pt\vjust{
\figtitle{}
\lineskip 0pt
\vskip -18pt
\halign to 115 pt{\square
#⊗\square
#⊗\square
#⊗\square
#⊗\square
#⊗\square
#⊗\square
#⊗\square
#⊗\square
#⊗\square #\cr
\ \ 1⊗\ \ 2⊗\ \ 2⊗\ \ 2⊗\ \ 2⊗\ \ 2⊗\ \ 2⊗\ \ 2⊗\ \ 2⊗\ \ 3\cr
\ \ 8⊗a8y⊗b8z⊗c8y⊗d8z⊗e8y⊗f8z⊗g8y⊗h8z⊗\ \ 4\cr
\ \ 8⊗a7z⊗b7y⊗c7z⊗d7y⊗e7z⊗f7y⊗g7z⊗h7y⊗\ \ 4\cr
\ \ 8⊗a6y⊗b6z⊗c6y⊗d6z⊗e6y⊗f6z⊗g6y⊗h6z⊗\ \ 4\cr
\ \ 8⊗a5z⊗b5y⊗c5z⊗d5y⊗e5z⊗f5y⊗g5z⊗h5y⊗\ \ 4\cr
\ \ 8⊗a4y⊗b4z⊗c4y⊗d4z⊗e4y⊗f4z⊗g4y⊗h4z⊗\ \ 4\cr
\ \ 8⊗a3z⊗b3y⊗c3z⊗d3y⊗e3z⊗f3y⊗g3z⊗h3y⊗\ \ 4\cr
\ \ 8⊗a2y⊗b2z⊗c2y⊗d2z⊗e2y⊗f2z⊗g2y⊗h2z⊗\ \ 4\cr
\ \ 8⊗a1z⊗b1y⊗c1z⊗d1y⊗e1z⊗f1y⊗g1z⊗h1y⊗\ \ 4\cr
\ \ 7⊗\ \ 6⊗\ \ 6⊗\ \ 6⊗\ \ 6⊗\ \ 6⊗\ \ 6⊗\ \ 6⊗\ \ 6⊗\ \ 5\cr}
\lineskip 1pt
\vskip -8pt
\caption{Standard algebraic notation}
}
\hfill
\vjust{
\figtitle{}
\lineskip 0pt
\vskip -18 pt
\chess \halign to 115pt{#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#\cr
1⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗3\cr
8⊗c⊗d⊗c⊗d⊗c⊗z⊗y⊗z⊗4\cr
8⊗d⊗c⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
8⊗c⊗d⊗y⊗b⊗y⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
8⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
8⊗y⊗z⊗y⊗z⊗y⊗j⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
7⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗5\cr}
\lineskip 1pt
\vskip -8pt
\caption{A sample kriegspiel position}
}
\hfill}
\vskip 3pt
\botinsert{\vskip 3pt
\hjust to size{\hfill
\vjust{
\figtitle{} % After k-d7 is illegal
\lineskip 0pt
\vskip -18 pt
\chess \halign to 115pt{#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#\cr
1⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗3\cr
8⊗y⊗z⊗c⊗d⊗c⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
8⊗y⊗z⊗y⊗b⊗y⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
8⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
8⊗y⊗z⊗y⊗z⊗y⊗j⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
7⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗5\cr}
\lineskip 1pt
\vskip -8pt
\caption{Position after K--d7 is illegal}
}
\hfill
\vjust{
\figtitle{} % after re2;
\lineskip 0pt
\vskip -18 pt
\chess \halign to 115pt{#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#\cr
1⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗3\cr
8⊗y⊗z⊗y⊗d⊗y⊗d⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗c⊗z⊗y⊗4\cr
8⊗y⊗z⊗y⊗b⊗y⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
8⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
8⊗y⊗z⊗y⊗z⊗i⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
7⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗5\cr}
\lineskip 1pt
\vskip -8pt
\caption{Position after R--e2 gives check}
}
\hfill
}}
The rules and conventions will be clear after we consider a simple example or
two. Suppose that White tries to move his king to d7 in the position of
\fig 2. If the referee says that such a move is
illegal, White sees the position in \fig 3. Suppose White now tries playing
his rook to e2 and the referee announces check. That means that the Black king
must be on e8. Black makes a legal move from e8, and it is White's move in the
position of \fig 4. White moves his king to c6, a move he knew was legal
before he tried it. After Black moves, his king can no longer be on d8; if
it was there, it had to move away. He can, however, still have a king on f8.
A king on f8 would also have had to move, but a king on f7 could move to f8.
The position after Black's next move appears in \fig 5. If the Black king is on
c8, White can mate by moving his rook to e8. \fig 6 shows that result.
Of course, if White plays that move, a king on f7 or f8 could capture the
rook and assure a draw.
The sequence of moves from \fig 2 to \fig 6 would appear as follows in
algebraic notation:\xskip
{\bd 1.\_\move Kd7{}, \move Re2\ch, 2.\_\move Kc6{}, 3.\_\move Re8\cm}.\xskip
Note, first of all, that there is no number before \move Re2\ch.
That is because \move Kd7{}\ was illegal and White was still looking for
his first move. The symbol \ch\ denotes a check and the symbol \cm\
denotes checkmate. A draw (stalemate or capture of the rook) is denoted by
the symbol \dr, which would appear in the same place as a \ch\ or a \cm.
\topinsert{\hjust to size{\hfill
\vjust{
\figtitle{} % after kc6
\lineskip 0pt
\vskip -18 pt
\chess \halign to 115pt{#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#\cr
1⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗3\cr
8⊗y⊗z⊗c⊗z⊗y⊗d⊗c⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗c⊗d⊗y⊗4\cr
8⊗y⊗z⊗a⊗z⊗y⊗d⊗c⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
8⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
8⊗y⊗z⊗y⊗z⊗i⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
7⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗5\cr}
\lineskip 1pt
\vskip -8pt
\caption{Position after K--c6}
}
\hfill
\vjust{
\figtitle{} % after re8#
\lineskip 0pt
\vskip -18 pt
\chess \halign to 115pt{#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#\cr
1⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗3\cr
8⊗y⊗z⊗c⊗z⊗i⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
8⊗y⊗z⊗a⊗z⊗y⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
8⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
8⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
7⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗5\cr}
\lineskip 1pt
\vskip -8pt
\caption{Position after R--e8 gives mate}
}
\hfill
}\vskip 3pt}
% analysis - beginning kings together
{\bd King and rook vs. king}.\xskip We will see that White can almost always
force a win in this endgame, even under kriegspiel conditions.
Black can draw only in certain starting positions where White cannot unite his king
and rook before Black captures the rook. Even if Black might be able
to capture the rook (given what White knows about the position), in
general, he will not. For if White does put his rook next to the Black king,
Black must guess where to move to make the capture. However, this article considers
only those positions where White can force mate against any (even the most
clairvoyant) defense.
\botinsert{\vjust{\vskip 2pt
\hjust to size{\hfill
\lower 7pt\vjust{
\figtitle{} % Both kings in one quadrant
\lineskip 0pt
\vskip -18 pt
\chess \halign to 115pt{#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#\cr
1⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗3\cr
8⊗c⊗d⊗c⊗d⊗c⊗d⊗y⊗z⊗4\cr
8⊗d⊗c⊗d⊗c⊗d⊗c⊗z⊗y⊗4\cr
8⊗c⊗d⊗c⊗d⊗c⊗d⊗y⊗z⊗4\cr
8⊗d⊗c⊗d⊗c⊗z⊗y⊗z⊗y⊗4\cr
8⊗c⊗d⊗c⊗d⊗y⊗b⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗j⊗y⊗4\cr
8⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
7⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗5\cr}
\lineskip 1pt
\vskip -8pt
\caption{Both kings in one quadrant (as seen by rook); White to move}
}
\hfill
\vjust{
\figtitle{} % Black king in 2 quadrants
\lineskip 0pt
\vskip -18 pt
\chess \halign to 115pt{#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#\cr
1⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗3\cr
8⊗c⊗z⊗c⊗d⊗c⊗d⊗c⊗d⊗4\cr
8⊗d⊗y⊗d⊗c⊗d⊗c⊗d⊗c⊗4\cr
8⊗c⊗z⊗c⊗d⊗c⊗d⊗c⊗d⊗4\cr
8⊗d⊗y⊗d⊗c⊗d⊗c⊗d⊗c⊗4\cr
8⊗c⊗z⊗c⊗d⊗c⊗d⊗c⊗d⊗4\cr
8⊗z⊗i⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
8⊗a⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
7⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗5\cr}
\lineskip 1pt
\vskip -8pt
\caption{White to move}
}
\hfill}}}
White's plan consists of several stages. First, he must make sure that his rook
is safe from capture. Then he plays to a position where all of the possible
squares for the Black king are in a rectangle
where one corner of that rectangle is a corner of the board and the opposite
corner is at the rook.
Further he wants his king in
that rectangle, too, keeping the Black king away from his rook. Then he forces
the Black king back until it can occupy only those squares on a single edge.
Finally, it is a fairly simple task to mate the Black king.
This article demonstrates a simple (but sometimes slow) way to force checkmate
looking at these types of positions:
$$\halign to size{\hjust{\bd \rgt{#}}⊗\hjust{\lft{\ #}}\cr
I⊗Both kings are in the same quadrant of the board as seen from the rook.\cr
II⊗The Black king is restricted to one or two quadrants of the board.\cr
III⊗The White rook is (can be) safe from capture.\cr}$$
Then it examines the positions of Type {\bd I} in more detail:
$$\halign to size{\hjust{\bd \rgt{#}}⊗\hjust{\lft{\ #}}\cr
IV⊗Black king confined to one rank (or file).\cr
V⊗Black king confined to two ranks.\cr
VI⊗Black king confined to three ranks.\cr
VII⊗Black king confined to four ranks.\cr
VIII⊗Black king confined to more than four ranks.\cr}$$
\vskip 2pt
\noindent
{\bd I. Both kings in the same quadrant}.\xskip
In \fig 7, both kings are above and to
left of the rook. White wants to confine the Black king to smaller and smaller
rectangles of the board. With this in mind, White tries to move his king to
e4 and his rook to f3. (He would be even happier to move his rook to the fourth
rank.) The game might continue {\bd 1.\_\move Ke4{}, \move Rf3{}
{\rm (or if \move Ke4{}\ is legal, continue as in A, below)},
2.\_\move Ke4{}, \move Ke3{}, \move Kf5{} {\rm (or B)}, 3.\_\move Ke4,
\move Rf4{}}. This particular sequence of moves reduces the smaller dimension
of the quadrant and results in a position like that after White's first move.
If \move Ke4{}\ was legal on move 2 or 3, then White reduced
the larger dimension and obtained a position similar to \fig 7.
There are other possible responses (by the referee) to some of White's attempts.
If 1.\_\move Ke4 is legal, we have line A: {\bd 2.\_\move Rf3 {\rm or}
2.\_\move Rf3\ch, 3.\_\move Rf4{}}. The second case results in a position
where the smaller dimension of the relevant quadrants is decreased, but the
Black king can be in either of two quadrants. The other possibility is that
2.\_$\ldots$\_\move Ke3{}\ is legal. Line B continues {\bd 3.\_\move Ke4{},
\move Rf4{}}. The first move is familiar. The second reduces the smaller
dimension, but results in a position in which the Black king is restricted
to one quadrant, while the White king is not in that quadrant.
A similar sequence of moves can be played from any analogous position
(except if the smaller dimension is one). It will be shown later that
the White king can end up in the same quadrant with the Black king in all cases
without increasing the smaller dimension. Therefore, White will be able to
restrict the king to the edge of the board.
% king in one or two quadrants
\botinsert{\vskip 2pt
\hjust to size{\hfill
\vjust{
\figtitle{} % king in 1 quadrant
\lineskip 0pt
\vskip -18 pt
\chess \halign to 115pt{#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#\cr
1⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗3\cr
8⊗y⊗z⊗y⊗z⊗c⊗d⊗c⊗d⊗4\cr
8⊗z⊗y⊗z⊗y⊗d⊗c⊗d⊗c⊗4\cr
8⊗y⊗z⊗y⊗z⊗c⊗d⊗c⊗d⊗4\cr
8⊗z⊗y⊗z⊗i⊗z⊗y⊗z⊗y⊗4\cr
8⊗y⊗z⊗y⊗z⊗a⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
8⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
7⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗5\cr}
\lineskip 1pt
\vskip -8pt
\caption{White to move}
}
\hfill
\vjust{
\figtitle{} % Rook needs protected
\lineskip 0pt
\vskip -18 pt
\chess \halign to 115pt{#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#\cr
1⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗3\cr
8⊗c⊗d⊗c⊗d⊗c⊗d⊗c⊗z⊗4\cr
8⊗d⊗c⊗d⊗c⊗d⊗c⊗d⊗y⊗4\cr
8⊗c⊗d⊗c⊗d⊗c⊗d⊗c⊗z⊗4\cr
8⊗d⊗c⊗d⊗c⊗d⊗c⊗d⊗y⊗4\cr
8⊗c⊗d⊗c⊗d⊗c⊗d⊗c⊗z⊗4\cr
8⊗d⊗c⊗d⊗c⊗d⊗c⊗d⊗y⊗4\cr
8⊗c⊗d⊗c⊗z⊗y⊗z⊗c⊗z⊗4\cr
8⊗d⊗c⊗d⊗y⊗b⊗y⊗z⊗i⊗4\cr
7⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗5\cr}
\lineskip 1pt
\vskip -8pt
\caption{Problem 1. How many moves save the rook?}
}
\hfill}}
\vskip 2pt
\noindent
{\bd II. Black king in one or two (adjacent) quadrants}.\xskip \fig 8 shows a
position where the Black king might be in either of two quadrants.
White wants to reach
a position similar to \fig 7, e.g. White king on b4, rook on a3, Black king
somewhere in ranks 4--8.
The first step is to move the rook (and the king if necessary) so that
one of the quadrants that might contain the Black king
has a side of length two. From \fig 8
play could proceed {\bd 1.\_\move Kb2{}, 2.\_\move Rc3{}}. Then White
plays his king into that quadrant, {\bd 3.\_\move Kb3{}, 4.\_\move Kb4{}}.
If the black king interferes, White simply retreats his
rook. Then both kings will be in the same quadrant, one with a dimension of
two. Finally, White moves his rook to the edge, {\bd 5.\_\move Ra3{}}.
White can ignore any checks that occur during that sequence of moves.
White can use the same plan if the Black king is restricted to one quadrant.
Sometimes, White doesn't need to move his king and rook over to the second and
third lines from the edge. In \fig 9 White plays his king around to c6
and moves his rook to c5 to get a position that arises after the first move in
section I. 1.\_\move Rd4{} would also result in a position with both kings
in the same quadrant, but the smaller dimension of the quadrant would be
larger. The game in \fig 9 could continue
{\bd 1.\_\move Kd4{}, 2.\_\move Kc5{}, 3.\_\move Kc6{}, 4.\_\move Rb5{}}.
% the rook is or can be safe; one rank, two rank
\vskip 2pt
\noindent
{\bd III. The rook is (or can be) safe}.\xskip
If the king and rook are united in the center of the board and the Black king
is not restricted as in the previous sections, then White wants to limit the
Black king in some way.
One position which resembles that in section I has the rook on a corner square,
e.g. h1, and his king nearby, e.g. g2.
So White moves his pieces toward the corner. If the Black king interferes,
then White knows that its position is restricted and proceeds as in section I
or II. Otherwise, White's pieces get to the corner and White can follow the
line in section I.
If the rook is subject to capture, White's first task is to protect the rook.
Usually, this is straightforward. Sometimes, there are several ways to
defend the rook. \fig{10} is a position with an undefended rook: can the
reader discover all of the ways to save it?\xskip(The answer appears at the
close of this article.)
\topinsert{\vskip 2pt
\hjust to size{\hfill
\vjust{
\figtitle{} % king on one rank
\lineskip 0pt
\vskip -18 pt
\chess \halign to 115pt{#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#\cr
1⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗3\cr
8⊗c⊗d⊗c⊗z⊗a⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗i⊗4\cr
8⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
8⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
8⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
7⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗5\cr}
\lineskip 1pt
\vskip -8pt
\caption{White to move}
}
\hfill
\vjust{
\figtitle{} % king confined to 2 ranks
\lineskip 0pt
\vskip -18 pt
\chess \halign to 115pt{#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#\cr
1⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗3\cr
8⊗c⊗d⊗c⊗d⊗y⊗z⊗y⊗z⊗4\cr
8⊗d⊗c⊗d⊗c⊗z⊗a⊗z⊗y⊗4\cr
8⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗j⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
8⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
8⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
7⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗5\cr}
\lineskip 1pt
\vskip -8pt
\caption{White to move}
}
\hfill}\vskip 2pt}
\vskip 2pt
\noindent
{\bd IV. Black king confined to one rank}.\xskip
The previous analysis does not apply
to positions with both kings in the same quadrant if the quadrant is a single line
on the edge. \fig {11} shows such a position. White can mate quickly by forcing
the king back into the corner and mating him with the rook. But White must be
a little careful to avoid stalemate. The game
could end
{\bd 1.\_\move Kd8{}, \move Rg7{}, 2.\_\move Kd8{}, 3.\_\move Kc7{},
{\rm (not 3.\_\move Kc8\dr)}, 4.\_\move Rg6{}, 5.\_\move Ra6\cm}. When the Black
king prevents a king move, the rook makes a move and the Black king must then
retreat.
\vskip 2pt
\noindent
{\bd V. Black king confined to two ranks}.\xskip
White can improve on the line given
in I if the black king is already restricted to two lines. It is unnecessary
to advance the rook along with the king when chasing the Black king into the
corner.
From \fig {12}, play could continue {\bd 1.\_\move Ke7{}, 2.\_\move Kd7{},
\move Kd6{}, 3.\_\move Kd7, 4.\_\move Kc7{}, \move Kc6{}, \move Kd8{},
5.\_\move Kc7{}, 6.\_\move Kb6{}, \move Kc8{}, 7.\_\move Ra6\cm}. If
5.\_\move Kc7{} is illegal White can play {\bd 5.\_$\ldots$\_\move Rh7{}}.
Two moves later,
7.\_\move Rh7\dr\ would be a serious mistake.
That mistake is easily avoided (and it is the only flaw in the simpler line
described in I).
% three rank,four rank
\botinsert{\vskip 2pt
\hjust to size{\hfill
\vjust{
\figtitle{} % king confined to 3 ranks
\lineskip 0pt
\vskip -18 pt
\chess \halign to 115pt{#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#\cr
1⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗3\cr
8⊗y⊗z⊗y⊗z⊗c⊗z⊗c⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗d⊗y⊗4\cr
8⊗y⊗z⊗y⊗z⊗a⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗i⊗z⊗y⊗4\cr
8⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
8⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
7⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗5\cr}
\lineskip 1pt
\vskip -8pt
\caption{White to move}
}
\hfill
\vjust{
\figtitle{} % king confined to 3 ranks
\lineskip 0pt
\vskip -18 pt
\chess \halign to 115pt{#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#\cr
1⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗3\cr
8⊗c⊗d⊗c⊗d⊗y⊗z⊗y⊗z⊗4\cr
8⊗d⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
8⊗c⊗z⊗a⊗z⊗y⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗j⊗y⊗z⊗y⊗4\cr
8⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
8⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
7⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗5\cr}
\lineskip 1pt
\vskip -8pt
\caption{Problem 2. How quickly can White force mate?}
}
\hfill}}
\noindent
{\bd VI. Black king confined to three ranks}.\xskip
There are a few ways to improve over the line in sections I and II when the
Black king is limited to three ranks or files. \fig {13} shows a position
after White has played \move Rf5\ch. The Black king is
in one of two quadrants. White can avoid the bother of going over to the
edge of the board with his pieces. He plays {\bd 1.\_\move Rf6{}, 2.\_\move
Ke7{}}. If \move Ke7{}\ is legal, the black king is in the quadrant on the
right; if it is illegal, the king is on the left.
\fig{14} shows another way White can save time in some positions. On
{\bd 1.\_\move Rd5\ch} Black may escape to the other side of the board and last
until White's twelfth move. How can White do better?\xskip
(See the answer below.)
\topinsert{
\hjust to size{\hfill
\vjust{
\figtitle{} % king confined to 4 ranks
\lineskip 0pt
\vskip -18 pt
\chess \halign to 115pt{#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#\cr
1⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗3\cr
8⊗c⊗d⊗c⊗d⊗c⊗d⊗y⊗z⊗4\cr
8⊗d⊗c⊗d⊗c⊗d⊗c⊗z⊗y⊗4\cr
8⊗c⊗d⊗c⊗z⊗y⊗z⊗y⊗z⊗4\cr
8⊗d⊗c⊗d⊗y⊗b⊗y⊗z⊗y⊗4\cr
8⊗y⊗z⊗y⊗z⊗y⊗z⊗i⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
8⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
7⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗5\cr}
\lineskip 1pt
\vskip -8pt
\caption{White to move}
}
\hfill
\vjust{
\figtitle{} % king confined to board
\lineskip 0pt
\vskip -18 pt
\chess \halign to 115pt{#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#\cr
1⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗3\cr
8⊗c⊗d⊗c⊗d⊗c⊗d⊗c⊗z⊗4\cr
8⊗d⊗c⊗d⊗c⊗d⊗c⊗d⊗y⊗4\cr
8⊗c⊗d⊗c⊗d⊗c⊗d⊗c⊗z⊗4\cr
8⊗d⊗c⊗d⊗c⊗d⊗c⊗d⊗y⊗4\cr
8⊗c⊗d⊗c⊗d⊗y⊗z⊗y⊗z⊗4\cr
8⊗d⊗c⊗d⊗c⊗z⊗a⊗z⊗y⊗4\cr
8⊗c⊗d⊗c⊗z⊗y⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗i⊗4\cr
7⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗5\cr}
\lineskip 1pt
\vskip -8pt
\caption{White to move}
}
\hfill}
\vskip 2pt}
\vskip 2pt
\noindent
{\bd VII. Black king confined to four ranks}.\xskip
\fig {15} is similar to \fig {13}. White wants to play \move Rf4{}.
If he plays it now and it is check,
Black's king will be in one of two quadrants, and White is too
far from the edge for the idea in \fig {13} to work. White can still avoid
the time and effort involved in the line of section II by playing
{\bd 1.\_\move Ke6{}}. If it is illegal,
he plays {\bd $\ldots$\_\move Rg5{}} and has reduced the smaller dimension.
If it is
legal he plays {\bd 2.\_\move Rf4{}}. If that results in a check, he is in
the line that follows \fig {13}.
\topinsert{\vskip 2pt
\hjust to size{\hfill
\vjust{
\figtitle{} % check on e--file
\lineskip 0pt
\vskip -18 pt
\chess \halign to 115pt{#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#\cr
1⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗3\cr
8⊗y⊗z⊗y⊗d⊗y⊗d⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗c⊗z⊗c⊗z⊗y⊗4\cr
8⊗y⊗z⊗y⊗d⊗y⊗d⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗c⊗z⊗c⊗z⊗y⊗4\cr
8⊗y⊗z⊗y⊗z⊗y⊗d⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗a⊗z⊗y⊗z⊗y⊗4\cr
8⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗j⊗y⊗z⊗y⊗4\cr
7⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗5\cr}
\lineskip 1pt
\vskip -8pt
\caption{Problem 3. White to move}
}
\hfill
\vjust{
\figtitle{} % k-f2 was illegal
\lineskip 0pt
\vskip -18 pt
\chess \halign to 115pt{#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#⊗#\cr
1⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗2⊗3\cr
8⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
8⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗4\cr
8⊗y⊗z⊗y⊗z⊗y⊗z⊗y⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗d⊗c⊗d⊗y⊗4\cr
8⊗y⊗z⊗y⊗z⊗y⊗z⊗c⊗z⊗4\cr
8⊗z⊗y⊗z⊗y⊗b⊗y⊗z⊗i⊗4\cr
7⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗6⊗5\cr}
\lineskip 1pt
\vskip -8pt
\caption{Problem 4. White to move}
}
\hfill}}
% Big regions
\vskip 2pt
\noindent
{\bd VIII. Black king is confined to more than four ranks}.\xskip
When the Black king is ``limited'' to a large section of the board,
White wants to shrink the region as quickly as he can.
\fig {16} shows the Black king limited to the entire board.
If the region is large enough, White can try to shrink the smaller
dimension (instead of the larger one, as in line I) of the quadrant the
Black king occupies. From \fig {16}, play could continue
{\bd 1.\_\move Rg1{}, 2.\_\move Ke3{}, 3.\_\move Rf1{}}. If either rook
move is a check, White next moves his rook two squares to the left to
produce a position in which both kings are in the same quadrant and
the smaller side is at worst four squares. \fig {17} is more difficult.
Again, the goal is to limit the Black king to at most four lines,
without playing king and rook to the edge of the board as in II.
\fig {18} arises from \fig{10} if 1.\_\move Kf2{}\ is illegal. How does
White play to restrict the Black king to a region of no more than four
lines?\xskip (Note that a $3\times4$ rectangle contains all possible squares
for the Black king, but the edges are not defined by the edges of the
board and the rook.)
% conclusion
\vskip 5pt
This article has shown that White, with a king and a rook, can checkmate
Black, who has only his king, in a game of kriegspiel. Sections IV and V show
that White can checkmate if he forces the Black king to the edge of the
board. Section III suggests that White can easily reach a position with
all possible positions of the Black king in a rectangle bounded by a rank
and file controlled by his rook and two edges of the board. Sections I and II
show that White can proceed from such a position to one where the rectangle
is smaller, where we say that
rectangle A ``smaller'' than a rectangle B if the smaller
dimension of A is less than the smaller dimension of B or if the smaller
dimensions are equal and the larger dimension of A is less than that of B.
The arguments suffice to show that White can mate from a wide variety
of positions, and on a rectangular board of arbitrarily large size.
By carefully studying the strategy detailed here, it can be shown that White
can force mate from the starting position in \fig{10} in at most xx moves.
Therefore there is no need to worry about games that are drawn because of the
``50 moves without a capture'' rule.
\vskip 10pt\noindent
{\bd Acknowledgments.}\xskip
This article is the result of one of the assignments in the class CS204
taught at Stanford University in the fall of 1978. I would like to
thank the professor of the course, Donald E. Knuth, who suggested the
problem of the kriegspiel ending after he had learned of it from some friends
in Germany; and the T.A. of the course, Chris Van Wyk,
who discussed this problem at length and helped prepare the article; and
the rest of the CS204 students who made several valuable suggestions.
\vskip 10pt\noindent
[bibliography]
\vskip 10pt
\noindent
{\bd Solutions}
\def\ansno#1{\vskip 2pt\noindent{\bd#1.\xskip\!}
\ansno1 Three moves save the rook, \move Rf1{}, \move Kf1{}, and \move Kf2{}.
After each of the last two, Black cannot take the rook because then White's
move would have been illegal. If the move is illegal, White can simply move
the rook away as he pleases.
\ansno2 White mates with {\bd 1.\_\move Kc7{}, \move Re6{}, {\rm (If \move Kc7{}\
is legal, White wins with a similar but shorter line.)} 2.\_\move Kd7{},
\move Kd6{}, 3.\_\move Ke7{}} and mates in nine more moves as in V.
\ansno3 White limits Black to a ``small'' rectangle with {\bd 1.\_\move Re4{},
\move Rc4{}}. If the first move is a check, White replies {\bd2.\_\move Re2{}}.
If the second move is a check, White continues {\bd3.\_\move Re4{}}.
\ansno4 White first moves the rook to safety, {\bd 1.\_\move Rh5{}, 2.\_\move Ra5{}}.
Then White moves his king near the rook {\bd 3.\_\move Kd2{}, 4.\_\move Kc3{}}.
If the second king move is illegal, he move his rook to safety again {\bd\move
Rg5{}}, and keeps trying to move his king near to it with {\bd 5.\_\move Ke3{},
\move Kc3{}, 6.\_\move Ra5{}}. If these two king moves are illegal, then
the Black king must be on d4. White plays a tempo move, {6.\_\move Rh5{}},
to make the king move and then tries again. This time, he must succeed.
If {\bd2.\_\move Kd2{}} is illegal, White plays {\bd\move Ra4{}, 3.\_\move Rh4} to produce
a position similar to what arises if it is legal.
\vfill
\eject